Bubble Sort, Selection Sort, এবং Insertion Sort গাইড ও নোট

1. Bubble Sort

Bubble Sort একটি সরল অ্যালগরিদম যা ধারাবাহিকভাবে তালিকার দুটিAdjacent উপাদান তুলনা করে তাদের সঠিক অর্ডারে সোয়ারাপ (swap) করে। এটি প্রতিটি পাসে বৃহত্তম বা ছোটতম উপাদানটি সঠিক স্থানে নিয়ে আসে, যেমন বুদ্বুদ একে অপরের সাথে উঠে আসে (তাই এর নাম 'Bubble Sort')।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (যখন তালিকা ইতিমধ্যেই সজ্জিত থাকে)
• Space Complexity: O(1)

Bubble Sort Implementation:

public class BubbleSort {
    // Method to perform Bubble Sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        // Traverse through all array elements
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // Last i elements are already sorted, so skip them
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no two elements were swapped by inner loop, the array is already sorted
            if (!swapped) {
                break;
            }
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Bubble Sort প্রতিটি পাসে সর্বোচ্চ উপাদানটি সঠিক স্থানে নিয়ে আসে।
• যদি কোনো ইটারেশনে কোনো সোয়ারাপ না ঘটে, তবে এটি নিশ্চিত করে যে অ্যারে ইতিমধ্যেই সজ্জিত এবং প্রোগ্রামটি তাড়াতাড়ি থেমে যাবে (যা best case O(n) প্রদান করে)।

2. Selection Sort

Selection Sort হল একটি সোজা এবং সহজ অ্যালগরিদম যা তালিকা থেকে প্রতিবার সর্বনিম্ন (বা সর্বোচ্চ) উপাদান খুঁজে বের করে এবং তাকে সঠিক স্থানে স্থানান্তরিত করে।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n²)
• Space Complexity: O(1)

Selection Sort Implementation:

public class SelectionSort {
    // Method to perform Selection Sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // Traverse through all array elements
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted part
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Selection Sort প্রতিটি ধাপে একটি উপাদান খুঁজে বের করে এবং সেটি তালিকার প্রথম অবস্থানে রেখে দেয়।
• এটি সর্বনিম্ন উপাদান খুঁজে পাওয়ার জন্য O(n²) সময় নেয়, তাই এটি ধীরগতি সম্পন্ন অ্যালগরিদম।

3. Insertion Sort

Insertion Sort হল একটি সরল অ্যালগরিদম যা তালিকার এক এক করে উপাদানগুলোকে একটি সাজানো অংশে সন্নিবেশ করে। এটি খুব সহজ কিন্তু ছোট আকারের তালিকার জন্য দ্রুত কাজ করে।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (যখন তালিকা ইতিমধ্যে সজ্জিত থাকে)
• Space Complexity: O(1)

Insertion Sort Implementation:

public class InsertionSort {
    // Method to perform Insertion Sort
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Traverse through 1 to n
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1] that are greater than key
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            arr[j + 1] = key;
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        insertionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Insertion Sort প্রতিটি উপাদানকে সঠিক জায়গায় সন্নিবেশ করিয়ে দেয়।
• এটি যেমন ছোট তালিকার জন্য উপযোগী, তেমনি ইতিমধ্যেই সজ্জিত তালিকার জন্যও দ্রুত (O(n) সময়) কাজ করে।
• Worst Case (যখন তালিকা উল্টোভাবে সজ্জিত থাকে) এর সময় O(n²) হয়।

তুলনা: Bubble Sort, Selection Sort, এবং Insertion Sort

সারাংশ

• Bubble Sort, Selection Sort, এবং Insertion Sort হল বেসিক, সহজ এবং সরল comparison-based sorting algorithms।
• এগুলির Time Complexity সাধারণত O(n²), তবে কিছু ক্ষেত্রে যেমন ইতিমধ্যে সজ্জিত তালিকা, এগুলি আরো কার্যকরী হতে পারে (যেমন Insertion Sort-এর জন্য O(n) best case)।
• Bubble Sort এবং Insertion Sort স্টেবল (Stable) হয়, অর্থাৎ তারা সমান উপাদানগুলিকে তাদের আসল অর্ডারে রেখে দেয়, তবে Selection Sort সাধারণত unstable হয়।
• ছোট আকারের তালিকার জন্য এই অ্যালগরিদমগুলি কার্যকরী, তবে বড় তালিকাগুলির জন্য দ্রুত অ্যালগরিদম (যেমন Merge Sort, Quick Sort) ব্যবহার করা উচিত।